1. Field of the Invention
The present invention relates to the compression and decompression of data and, more particularly, to the compression and decompression of data in combination with error correction coding (ECC) in a computer peripheral environment.
2. Statement of the Problem
Two basic architectural approaches to the compression/decompression (CD) of data involving ECC are conventionally available.
In FIG. 1, a first prior art computer configuration is shown. A host computer 10 is interconnected with the conventional input/output (I/O) channel 20. Also connected is a disk 30 which is interconnected through a disk adapter 40 to the I/O channel 20. A peripheral device 50 connected through a peripheral adapter 60 also accesses the I/O channel 20. Internal to the host computer 10 is a host RAM 70 which contains the application program data buffers 74 and the application program 78. The host RAM 70 is connected to the I/O channel 20 over an I/O data bus 22 and an I/O control bus 24. Host computer 10 also contains CPU circuitry 80 which is connected to the I/O channel over the data bus 22 and the control bus 24. Finally, the host computer contains a direct memory access (DMA) controller 90 which also accesses the I/O control bus 24 and an I/O data bus 22. In this prior art approach, the disk 30 could, for example, correspond to the hard disk internal to the computer 10. The hard disk 30 has an application program file 31 and other files. The disk 30 delivers control signals over bus 32 and data signals over bus 34 to the disk adapter 40. The disk adapter 40 has disk adapter circuitry 42 and a disk adapter RAM 44 for providing the communications between the host computer 10 and the disk 30. This is a conventional architecture and the transfer of data between the host computer 10 and the disk 30 occurs in an uncompressed format without error correction.
The peripheral 50 could be any suitable peripheral such as, for example, a tape backup or another disk. The peripheral 50 communicates with its peripheral adapter 60 over a control bus 52 and a data bus 54. In the peripheral adapter 60 is a compression/decompression (CD) co-processor 62 which communicates over a control and data bus with a compressor/decompression RAM 64. The CD co-processor 62 also communicates over a bus with ECC RAM 66 which is under the control of an ECC co-processor 65. The ECC co-processor 65 communicates with the ECC RAM 64 over control and data buses. Finally, the ECC RAM 64 delivers compressed ECC data over bus 67 to a peripheral interface (PI) 68 which delivers the compressed ECC data over the data bus 54 to the peripheral device 50. In this prior art approach, the peripheral adapter 60 utilizes separate co-processors 62 and 65 with associated RAM 64 and 66 to accomplish the compression/decompression and error correction coding activities. This is an expensive approach to compression/decompression and ECC since for each peripheral device 50, different co-processors 62 and 65 would have to be utilized. Even for one peripheral device 50, the expense is undesirable.
In FIG. 1, the following data flow occurs. The host computer 10 delivers data from the application program data buffers RAM 74 over the I/O data bus 22 and into the peripheral adapter 60. This is delivered into the CD co-processor 62. The algorithm for performing compression and decompression is found in the CD co-processor 62 and RAM 64 and is used by the co-processor in the compression/decompression process. The second transfer occurs from the CD co-processor 62 to the ECC RAM 66 wherein the ECC co-processor 65 provides error correction coding to the data in the RAM 66. The third transfer is from the ECC RAM 66 to the peripheral interface 68. The third transfer transfers the compressed ECC data. Finally, the fourth transfer delivers the compressed ECC data from the peripheral interface 68 over the data bus 54 to the peripheral device 50. Of course, decompression occurs opposite to the above transfer and data flow.
In the prior art approach of FIG. 1, the disk 30 contains the application program module 31 which is loaded into the host RAM 70 by the host computer 10. The CPU 80 and/or the DMA controller 90 controls the first data transfer from the host RAM 70 to the peripheral adapter 60. It is to be expressly understood that in some embodiments, the CD co-processor 62, CD RAM 64, ECC co-processor 65, and ECC RAM 66, could be moved to the peripheral device 50.
In FIG. 2, a conventional approach is shown wherein both compression/decompression and ECC are performed in software.
In FIG. 2, similar numerical references of FIG. 1 are used to identify similar components. However, in this environment, the host RAM 70 also includes compression/decompression RAM 75, compression/decompression program RAM 77, ECC RAM 76, and ECC program RAM 72. This is all software which is loaded internally to the host RAM 70 from disk 30 where the CD program module 33 and ECC program module 35 reside along with the application program module in the application's program file 31. Hence, when it is desired to deliver compressed ECC data to the peripheral device 50, the application program file in disk 30 is conventionally loaded into the appropriate section 74 of RAM 70 (as shown in FIG. 2). The transfer of data occurs in the following sequence. The first transfer involves the delivery of data from the application program data buffers RAM 74 over the data bus 22 in the I/O channel and into the CD program RAM 77 where it is compressed by the CD algorithm. After compression, the second transfer is the transfer of the data from the CD program RAM 77 onto the I/O data bus 22 for delivery into the ECC RAM 76 where error correction coding occurs under direction of the algorithm in the ECC program RAM 72. The third transfer is from the ECC RAM 76 over the I/O data bus 22 to the peripheral adapter 60. This transfer is a transfer of compressed ECC data. The first two transfers are conventionally under control of the CPU 80. The third transfer is conventionally under control of either the CPU 80 or the DMA controller 90. The peripheral interface 68 then communicates the compressed ECC data to the peripheral device 50. Again, decompression occurs in the reverse sequence.
FIG. 1 represents a prior art approach wherein both compression/decompression and ECC occur in hardware external electrically to the host computer 10. As mentioned, the requirement for separate hardware in each peripheral adapter (or peripheral) became expensive. The prior art approach of FIG. 2 reduces the expense by placing both the compression/decompression and ECC activities as software internally in the host RAM of the host computer. The software modules are located in the disk 30. Hence, upon calling up the application program file 31, the CD and ECC modules are downloaded from the disk 30 into the host RAM 70. While the prior art approach of FIG. 2 achieved the goal of reducing the hardware expense associated with the approach of FIG. 1, it did not provide an optimum solution. The compression/decompression software program degraded overall data transfer speed to an unacceptable level. For example, when the host computer is a 286 chip operating at 8 MHz to compress 40.5 mega-bytes of data to a 1 megabit/sec tape drive, the software compression approach of FIG. 2 takes approximately 20-25 minutes whereas the hardware compression circuit of FIG. 1 takes approximately 7-9 minutes. The CPU 80 was required to implement the compression/decompression process and, therefore, a substantial time penalty occurred. In applications where time was not a factor, the prior art approach of FIG. 2 fully satisfied the cost reduction need of FIG. 1.
A need exists for performing compression/decompression and ECC in an architectural arrangement that not only reduces the expense of FIG. 1 (i.e., external CD and ECC hardware), but also reduces the time problems associated with doing compression/decompression in the prior art approach of FIG. 2 (i.e., CD and ECC performed by internal software). An optimum architectural arrangement would reduce the cost associated with FIG. 1 and substantially speed up the compression/decompression activity of FIG. 2.
3. Results of Patentability Search
A patentability search was directed towards the solution of the above stated problem. The results of that search are set forth below.
______________________________________ INVENTOR PATENT NO. ISSUE DATE ______________________________________ Iida 4,408,301 10-4-83 Reitsma 4,622,585 11-11-86 Cotton et al 4,688,108 8-18-87 Hamilton et al. 4,897,717 1-30-90 Janku 4,902,881 2-20-90 O'Brien et al. 4,929,946 5-29-90 Hamilton et al. 4,951,139 8-21-90 ______________________________________
U.S. Pat. No. 4,408,301 sets forth a picture information filing system wherein data from a character pattern generator and picture scanning device is compressed onto a magnetic tape. The data from the magnetic tape is then decompressed for a picture display or a picture element memory.
U.S. Pat. No. 4,622,585 sets forth a compression/decompression system for transmitting and receiving compressed picture information that is arranged in rows and columns of pixels. The data which is scanned in is compressed and may be selectively stored in an optical disk, magnetic disk, or RAM. The compressed data from storage is then delivered through a decompressor into a CRT or printer.
U.S. Pat. No. 4,688,108 pertains to a high resolution graphic system for a video/teleconferencing system. Again, data from a scanner is compressed and delivered into memory. The compressed data from memory is delivered through a decompressor for display.
U.S. Pat. No. 4,897,717 sets forth a computer base video compression system which utilizes a subsystem in the host computer to compress video images. The '717 patent utilizes a special circuit in its compression system. A frame grabber is used to input and output analog information from a memory internal to the frame grabber. That memory is connected to a second memory in the special circuit which enables a fast transfer of data from one memory to the other memory. The memory in the special circuit then provides the information to a compression unit which delivers compressed data to the host memory. Likewise, the compressed data in the host memory can be transferred back into memory in the special circuit which accesses a decompression unit for delivery of decompressed data to the frame grabber. The '717 approach utilizes fast transfer rates. U.S. Pat. No. 4,951,139 is related to the '717 patent.
U.S. Pat. No. 4,902,881 relates to a parallel process communication terminal network wherein a high speed co-processor is used to implement a data compression/decompression algorithm.
U.S. Pat. No. 4,929,946 pertains to an adaptive data compression apparatus including run length and coding for a tape drive system. This corresponds to the prior art approach of FIG. 1 wherein data compression and decompression occurs on the peripheral adapter between the peripheral device and the host.
None of the above patented approaches solve the specific problem set forth above of providing an optimal design configuration involving use of error correction coding and wherein the expense of the FIG. 1 prior art approach is reduced and the time to perform compression/decompression is reduced